//https://leetcode.cn/problems/fruit-into-baskets/
//⽔果成篮
class Solution 
{
public:
    int totalFruit(vector<int>& fruits) 
    {
        unordered_map<int,int> hash;
        int ret = 0;
        int left = 0;
        int right = 0;

        while(right < fruits.size())
        {
            hash[fruits[right]]++;
            while(hash.size() > 2)
            {
                hash[fruits[left]]--;
                if(hash[fruits[left]] == 0)
                {
                    hash.erase(fruits[left]);
                }
                left++;
            }
            ret = max(ret,right - left + 1);
            right++;
        }
        return ret;
    }
};

//https://leetcode.cn/problems/find-all-anagrams-in-a-string/
//找到字符串中所有字⺟异位词
class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        vector<int> ret;
        int hash1[26] = { 0 };
        int hash2[26] = { 0 };
        for(auto e:p) hash1[e - 'a'] ++;
        int left = 0;
        int right = 0;
        int count = 0;
        int len = p.size();
        while(right < s.size())
        {
            char in = s[right] - 'a';
            if(++hash2[in] <= hash1[in]) count++;

            if(right - left + 1 > len)
            {
                char out = s[left] - 'a';
                if(hash2[out]-- <= hash1[out]) count--;
                left++;
            }

            if(count == len)
            {
                ret.push_back(left);
            }
            right++;
        }

        return ret;
    }
};

//串联所有单词的⼦串
//https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) 
    {
        vector<int> ret;
        unordered_map<string,int> hash1;
        for(auto& e:words) hash1[e]++;

        int m = words.size();//字符串的个数
        int len = words[0].size();//字符串的长度
        int left = 0;
        int right = 0;
        int count = 0;
        for(int i = 0; i < len; i++)
        {
            unordered_map<string,int> hash2;
            left = i;
            right = i;
            count = 0;
            while(right + len <= s.size())
            {
                string in = s.substr(right,len);
                hash2[in]++;
                if(hash1.count(in) && hash2[in] <= hash1[in]) count++;
                if(right - left + 1 > m * len)
                {
                    string out = s.substr(left,len);
                    if(hash1.count(out) && hash2[out] <= hash1[out]) count--;
                    hash2[out]--;
                    left += len;
                }
                if(count == m)
                {
                    ret.push_back(left);
                }
                right+=len;
            }

        }
        return ret;
    }
};

// 最⼩覆盖⼦串
// https://leetcode.cn/problems/minimum-window-substring/
class Solution {
public:
    string minWindow(string s, string t) 
    {
        int kinds = 0;
        int hash1[128] = {0};
        for(auto e : t)
            if(hash1[e]++ == 0) kinds++;

        int hash2[128] = {0};
        int minlen = INT_MAX;
        int begin = -1;
        for(int left = 0,right = 0,count = 0;right <s.size(); right++)
        {
            char in = s[right];
            if(++hash2[in] == hash1[in]) count++;
            while(count == kinds)
            {
                if(right - left + 1 < minlen)
                {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if(hash2[out]-- == hash1[out]) count--;
            }
        }

        if(begin == -1)
        {
            return "";
        }
        return s.substr(begin,minlen);
    }
};


